import java.util.*;
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class project {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if(left==right){
            return head;
        }
        ListNode newHead=new ListNode(-1);
        newHead.next=head;
        ListNode prev=newHead;
        for(int i=0;i<left-1;i++){
            prev=prev.next;
        }
        ListNode cur=prev.next;
        for(int i=0;i<right-left;i++){
            ListNode curNext=cur.next;
            cur.next=curNext.next;
            curNext.next=prev.next;
            prev.next=curNext;
        }
        return newHead.next;
    }











//    public static void sort(int[] arr){
//        Mysort(arr,0,arr.length-1);
//    }
//    public static void Mysort(int[] arr,int left,int right){
//        if(left>=right){
//            return;
//        }
//        int index=partition(arr,left,right);
//        Mysort(arr,index+1,right);
//        Mysort(arr,left,index-1);
//    }
//    public static int partition(int[] arr,int left,int right){
//        int tmp=arr[left];
//        while (left<right){
//            while (left<right&&arr[right]>=tmp){
//                right--;
//            }
//            arr[left]=arr[right];
//            while (left<right&&arr[left]<=tmp){
//                left++;
//            }
//            arr[right]=arr[left];
//        }
//        arr[left]=tmp;
//        return left;
//    }

















//    public static void main(String[] args) {
//        int[] arr=new int[]{9,8,7,6,5,4,3,2,1};
//        sort(arr);
//
//        System.out.println(Arrays.toString(arr));
//    }
//    public static void sort(int[] arr){
//        Mysort(arr);
//        int end=arr.length-1;
//        while (end>=0){
//            swap(arr,end,0);
//            shiftDown(arr,0,end);
//            end--;
//        }
//    }
//    public static void Mysort(int[] arr){
//        for(int i=(arr.length-1)/2;i>=0;i--){
//            shiftDown(arr,i,arr.length);
//        }
//    }
//    public static void shiftDown(int[] arr,int start,int end){
//        int left=start*2+1;
//        while (left<end){
//            if(left+1<end&&arr[left+1]>arr[left]){
//                left++;
//            }
//            if(arr[left]>arr[start]){
//                swap(arr,left,start);
//                start=left;
//                left=start*2;
//            }else{
//                break;
//            }
//        }
//    }
//    public static void swap(int[] arr,int x,int y){
//        int tmp=arr[x];
//        arr[x]=arr[y];
//        arr[y]=tmp;
//    }
















    public int minimumRounds(int[] tasks) {
        Map<Integer,Integer> map=new HashMap<>();
        for(int key:tasks){
            map.put(key,map.getOrDefault(key,0)+1);
        }
        int ret=0;
        for(Map.Entry<Integer,Integer> entry:map.entrySet()){
            if(entry.getValue()==1){
                return -1;
            }
            if(entry.getValue()<=3){
                ret++;
            }else{
                int  model=entry.getValue()%3;
                ret+=model==0?entry.getValue()/3:entry.getValue()/3+1;
            }
        }
        return ret;
    }




















    public long waysToBuyPensPencils(int total, int cost1, int cost2) {
        long ret=0;
        int surplus=total/cost1;
        for(int i=0;i<=surplus;i++){
            ret+=(total-i*cost1)/cost2+1;
        }
        return ret;
    }


















    public String digitSum(String s, int k) {
        while (s.length()>k){
            StringBuilder sb=new StringBuilder();
            int index=0;
            while (index<s.length()){
                String str=null;
                if(index+k>s.length()){
                    str=s.substring(index,s.length());
                }else{
                    str=s.substring(index,index+k);
                }
                int sum=0;
                for(int i=0;i<str.length();i++){
                    sum+=Integer.parseInt(String.valueOf(str.charAt(i)));
                }
                sb.append(sum);
                index+=k;
            }
            s=sb.toString();
        }
        return s;
    }



















    public int findClosestNumber(int[] nums) {
        int min=Integer.MAX_VALUE;
        int index=0;
        for(int i=0;i<nums.length;i++){
            int tmp=Math.abs(nums[i]-0);
            if(tmp<min||(tmp==min&&nums[i]>nums[index])){
                min=tmp;
                index=i;
            }
        }
        return nums[index];
    }

















    public List<Integer> lexicalOrder(int n) {
        List<Integer> list=new ArrayList<>();
        dfs(list,0,1,n);
        return list;
    }
    public void dfs(List<Integer> list,int tmp,int start,int end){
        if(tmp>end){
            return;
        }
        for(int i=start;i<10;i++){
            int ret=i+tmp;
            if(ret<=end){
                list.add(ret);
                dfs(list,ret*10,0,end);
            }
        }
    }
}
